package alo.p6.work2;

/**
 * @ClassName KaryTreeNode
 * @Description 根据满k叉树的前序遍历构建k叉树
 * @Author Fanxc
 * @DATE 2021/2/3 20:13
 * @Version 1.0
 */
public class BuildKaryTreeNode {
    //k叉树结点的定义
    class KaryTreeNode{
        private int data;
        private KaryTreeNode[] child;

        public KaryTreeNode(int k) {
            child=new KaryTreeNode[k];
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public KaryTreeNode getChild(int i) {
            return child[i];
        }

        public void setChild(int i,KaryTreeNode childNode) {
            child[i] = childNode;
        }
    }
    //索引变量Ind
    int Ind=0;
    //第i个位置结点的孩子结点位置应该在k*i+1~k*i+k个位置上
    KaryTreeNode buildKaryTree(int[] A,int n,int k){
        if (n<=0){
            return null;
        }
        KaryTreeNode newNode=new KaryTreeNode(k);
        if (newNode==null){
            System.out.println("Memory Error!");
            return null;
        }
        newNode.setData(A[Ind]);
        for (int i = 0; i < k; i++) {
            //Ind位置上的孩子在n之间（即存在）
            // 前序遍历递归到底，直到叶子结点，进入else情况，然后返回
            if (k*Ind+i<n){
                Ind++;
                newNode.setChild(i,buildKaryTree(A,n,k));
            }
            //不存在，设置孩子为null
            else {
                newNode.setChild(i,null);
            }
        }
        return newNode;
    }
}
